#include<iostream>
using namespace std;
  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* a1 = nullptr, * a2 = nullptr, * start1 = nullptr, * start2 = nullptr;
        while (head) {
            if (head->val < x) {
                if (a1 == nullptr) {
                    a1 = head;
                    start1 = head;
                }
                else {
                    a1->next = head;
                    a1 = head;
                }
            }
            else {
                if (a2 == nullptr) {
                    a2 = head;
                    start2 = head;
                }
                else {
                    a2->next = head;
                    a2 = head;
                }
            }
            head = head->next;
        }
        if (a1)
            a1->next = start2;
        if (a2)
            a2->next = nullptr;
        return start1 == nullptr ? start2 : start1;
    }
};